package com.datastructures.tree;

/**
 * 线索化二叉树
 * @author MaoLin Wang
 * @date 2019/11/616:05
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(3);
        TreeNode treeNode3 = new TreeNode(6);
        TreeNode treeNode4 = new TreeNode(8);
        TreeNode treeNode5 = new TreeNode(10);
        TreeNode treeNode6 = new TreeNode(14);

        root.lchild=treeNode2;
        root.rchild=treeNode3;
        treeNode2.lchild=treeNode4;
        treeNode2.rchild=treeNode5;
        treeNode3.lchild=treeNode6;

        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.thrededNodes();

        //测试:10节点
        TreeNode leftNode = treeNode5.lchild;
        TreeNode rchild = treeNode5.rchild;
        System.out.println("10号节点的前驱节点:"+leftNode.no);
        System.out.println("10号节点的后继节点:"+rchild.no);
        threadedBinaryTree.thrededList();
    }
}

//定义线索化二叉树
class ThreadedBinaryTree {
    private TreeNode root;

    //在递归进行线索化时，pre总是保留前一个节点
    private TreeNode pre=null;

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void thrededNodes(){
        this.thrededNodes(root);
    }

    /**
     * 遍历线索化二叉树
     */
    public void thrededList(){
        //定义一个遍历，存储当前遍历的节点，从root开始
        TreeNode node=root;
        while (node!=null){
            //循环找到lType ==1的节点，第一个就是8节点
            while (node.leftType ==0){
                node=node.lchild;
            }
            //打印当前节点
            System.out.println(node);
            //如果当前节点的右指针指向的是后继节点，就一直输出
            while (node.rightType==1){
                node=node.rchild;
                System.out.println(node);
            }
            //替换这个遍历的接地那
            node=node.rchild;
        }
    }
    /**
     * 中序线索化方法
     * @param node 当前需要线索化的节点
     */
    public void thrededNodes(TreeNode node){
        if (node==null){
            return;
        }
        //1.先线索化左子树
        thrededNodes(node.lchild);
        //2.线索化当前节点

        //2.1处理当前节点的前驱节点
        if (node.lchild ==null){
            //让当前节点的左指针指向前驱节点
            node.lchild=pre;
            //修改当前节点的左指针的类型
            node.leftType=1;
        }
        //2.2处理后继节点
        if (pre!=null && pre.rchild==null){
            //让前驱节点的右指针指向当前节点
            pre.rchild=node;
            //修改前驱节点的右指针类型
            pre.rightType=1;
        }
        //每处理一个节点后，让当前节点时下一个节点的前驱节点
        pre=node;
        //3.线索化右子树
        thrededNodes(node.rchild);
    }

}

class TreeNode {
    public int no;
    public TreeNode lchild;
    public TreeNode rchild;

    /**
     * 1.leftType:0  -> 指向左子树
     * 2.leftType:1  -> 指向前驱节点
     */
    public int leftType;

    /**
     * 1.rightType:0  -> 指向右子树
     * 2.rightType:1  -> 指向后驱节点
     */
    public int rightType;
    public TreeNode() {
    }

    public TreeNode(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "no=" + no +
                '}';
    }




}


